package demo5;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-09-01
 * Time: 10:22
 */
public class TestDemo1 {

    //给你一个面值数组,每一个面值都可以使用无限张,返回组成aim的方法数有多少???

    public static int ways3(int[] arr,int aim){
        return process3(arr,0,aim);
    }

    public static int process3(int[] arr,int index, int rest){
        if(index== arr.length){
            return rest == 0 ? 1: 0;
        }
        int ways = 0;
        for(int zhang =0;zhang * arr[index]<=rest;++zhang){
            ways += process3(arr,index+1,rest);
        }
        return ways;
    }

    public static int waysDp(int[] arr,int aim){
        int N = arr.length;
        int[][] dp = new int[N+1][aim+1];
        for(int index = N-1 ;index>=0;--index){
            for(int rest =0;rest<=aim;++rest){
                int ways =0;
                for(int zhang =0;zhang * arr[index]<=rest;++zhang){
                    ways +=  dp[index+1][rest];
                }
                dp[index][rest] = ways;
            }
        }
        return dp[0][aim];
    }
    public static void main(String[] args) {

    }


}
